/*
 * @lc app=leetcode.cn id=214 lang=golang
 *
 * [214] 最短回文串
 */

// @lc code=start
// 这题可以将题目转换为寻找前面的最长回文子串
// 如果题目可以在后面插入，则可以转换为寻找字符串的最长回文子串
// 找到回文子串后，剩下的子串逆转加在前面就是最短的回文串了
// 将字符串逆转后，逆转的字符串的后缀与原字符串的前缀之间的重合的最长长度就是前面的最长回文子串

import (
	"strings"
)

func shortestPalindrome(s string) string {
	reversion := rever(s)
	n := len(s)
	i := n - 1
	l := 0
	for ; i >= 0; i-- {
		if strings.HasPrefix(s, reversion[i:]) {
			l = n - i
		}
	}

	return rever(s[l:]) + s
}

func rever(s string) string {
	n := len(s)
	rs := []rune(s)
	for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
		rs[i], rs[j] = rs[j], rs[i]
	}
	return string(rs)
}

// @lc code=end
